package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/20 16:12
 * @description <p>和大于或等于 k 的最短子数组 </p>
 */

/**
 * 题目：输入一个正整数组成的数组和一个正整数 k，请问数组中和大于
 * 或等于 k 的连续子数组的最短长度是多少？如果不存在所有数字之和大于
 * 或等于 k 的子数组，则返回 0。例如，输入数组[5, 1, 4, 3]，k 的值为 7，和
 * 大于或等于 7 的最短连续子数组是[4, 3]，因此输出它的长度 2
 */
public class toOffer2_2_8 {
    public static void main(String[] args) {
        int[] nums = {5, 1, 4, 3};
        System.out.println(fun(nums, 7));
    }

    /**
     * 两个指针构成一个数组、slow指向新数组的开头、fast指向新数组的结尾。
     * 开始时候快慢指针都指向数组里的第一个数，fast指针会一直走，直到指向数组里的最后一个数（循环）
     * 每次fast指向一个新的数，都需要将当前两个指针构成的数组的sum值与k进行比较
     * 如果sum >= k，由于数组里都是正数，所以可以让slow右移，令sum的值减少，判断返回的result的值与此时fast - slow + 1的大小。
     *
     * @param nums
     * @param k
     * @return
     */
    public static int fun(int[] nums, int k) {
        int result = nums.length;
        int slow = 0;
        int fast = 0;
        int sum = 0;

        while (fast < nums.length) {
            sum += nums[fast];
            while (sum >= k && slow <= fast) {
                //sum >= k 证明选的数组大了，可以尝试减数，slow右移
                result = Math.min(fast - slow + 1, result);
                sum -= nums[slow];
                slow++;
            }
            fast++;
        }

        return result;

    }
}
